﻿// exchange_linkedlist_node.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <stack>

using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* CreateLinkedList(vector<int>vec)
{
    ListNode* head = new ListNode(vec[0]);
    ListNode* curr = head;
    for (int i = 1; i < vec.size(); i++) {
        curr->next = new ListNode(vec[i]);
        curr = curr->next;
    }
    return head;
}

void CheckLinkedList(ListNode* head)
{
    ListNode* curr = head;
    while (nullptr != curr)
    {
        cout << curr->val << ' ';
        curr = curr->next;
    }
}

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (nullptr == head) return nullptr;
        if (nullptr == head->next) return head;

        ListNode* fakenode = new ListNode(0);
        fakenode->next = head;

        ListNode* prevnode = fakenode;

        while (nullptr != prevnode->next && nullptr != prevnode->next->next)
        {
            ListNode* node1 = prevnode->next;
            ListNode* node2 = prevnode->next->next;

            prevnode->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            prevnode = node1;
        }
        ListNode* result = fakenode->next;
        return result;
    }

    ListNode* rotateRight(ListNode* head, int k) {
        if (0 == k) return head;
        if (nullptr == head) return nullptr;
        if (nullptr == head->next) return head;

        int list_size = 1;
        ListNode* count_node = head;
        while (nullptr != count_node->next)
        {
            count_node = count_node->next;
            list_size++;
        }
        
        int rotate_count = k % list_size;
        if (rotate_count == 0) return head;

        ListNode* fakenode = new ListNode(0);
        fakenode->next = head;
        while (rotate_count--)
        {
            ListNode* curr_head = fakenode->next;
            ListNode* prev_tail = curr_head;
            while (nullptr != prev_tail->next->next)
            {
                prev_tail = prev_tail->next;
            }
            ListNode* tail = prev_tail->next;
            prev_tail->next = nullptr;

            tail->next = curr_head;
            fakenode->next = tail;
        }
        return fakenode->next;
    }


    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> result_vec;

        ListNode* curr = head;
        while (nullptr != curr->next)
        {
            cout << "curr: " << curr->val << endl;
            ListNode* curr_next = curr->next;
            

            while (nullptr != curr_next)
            {
                if (curr_next->val > curr->val)
                {
                    int bigger = curr_next->val;
                    result_vec.push_back(bigger);
                    break;
                }
                else {
                    curr_next = curr_next->next;
                }
            }
            if (nullptr == curr_next) {
                result_vec.push_back(0);
            }

            curr = curr->next;
        }
        result_vec.push_back(0);

        return result_vec;

    }


    vector<int> nextLargerNodes1(ListNode* head){
        vector<int> result;
        stack<pair<int, int>> my_stack;

        ListNode* curr = head;
        int index = -1;

        while (nullptr != curr)
        {
            index++;
            result.push_back(0);
            while (!my_stack.empty())
            {
                int top_val = my_stack.top().first;
                if (top_val < curr->val)
                {
                    int changed_index = my_stack.top().second;
                    result[changed_index] = curr->val;
                    my_stack.pop();
                }
                else {
                    break;
                }
            }
            my_stack.emplace(curr->val, index);
            curr = curr->next;
        }
        return result;
    }
};

int main()
{
    class Solution solution;
    vector<int> vec{ 2,1,5 };
    ListNode* head = CreateLinkedList(vec);
    
    //CheckLinkedList(head);

    //ListNode* result = solution.swapPairs(head);
    //ListNode* result = solution.rotateRight(head, 5);

    //CheckLinkedList(result);

    vector<int> result_vec = solution.nextLargerNodes1(head);

    cout << "result_vec: " << endl;
    for (auto& item : result_vec)
    {
        cout << item << ' ';
    }
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
